if __name__ == "__main__":
    tcases = int(input())
    result=[]
    for case in range(tcases):
        n = int(input().strip())
        a0, a1, a2, i, f = 0, 1, 1, 3, 0
        while 3 <= i <= n:
            f = a0 + a1 + a2
            a0, a1, a2 = a1, a2, f
            i += 1
        if n==1 or n==2:
            f=1
        result.append(f)
    print(result)
    count=0
    for each in result:
        print("case #%d:\n%d" % (count,each))
        count+=1
